/*
 * Copyright (c) Huawei Technologies Co., Ltd. 2021-2021. All rights reserved.
 */

package MonotonicStack;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 84. 柱状图中最大的矩形
 * 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
 *
 * 求在该柱状图中，能够勾勒出来的矩形的最大面积
 *
 * @author z00611952
 * @since 2021/9/23
 */
public class leetcode84_largestRectangleArea {
    public static void main(String[] args) {
        Solution1 solution = new Solution1();
        int[] heights = {2,1,5,6,2,3};
        System.out.println(solution.largestRectangleArea(heights));
    }

}

class Solution1 {
    public int largestRectangleArea(int[] heights) {
        int[] h = new int[heights.length+2];
        // 左右两边添加0，表示第一个元素不能向左边扩散，最后一个元素不能向右边扩
        h[0] = 0;
        h[h.length-1] = 0;
        for(int i = 0; i < heights.length; i++){
            h[i+1] = heights[i];
        }
        Deque<Integer> stack = new ArrayDeque<>();
        int res = 0;
        stack.push(0);
        for(int i = 1; i < h.length; i++){
            while(!stack.isEmpty() && h[i] < h[stack.peek()] ){
                // 当前需要计算的柱子
                int hh = h[stack.pop()];
                //  左边界
                int left = stack.peek();

                res = Math.max(res, (i - left - 1) * hh);
            }
            stack.push(i);
        }
        return res;

    }
}
